// 递归搜索与回溯 - 决策树问题
// 当一个题目可以使用决策树画出来，那么也可以通过递归的方法解决
// 画决策树，要保证不重不漏
// 使用全局变量进行统计，避免递归函数头传参问题
// 设计递归函数头，是否需要记录本次决策的位置，层数，个数等信息
// 回溯时注意本层计算完成后，直接在本层回溯，返回上一个位置
// 经典题目：全排列，子集

// 例题 3：
// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
//
//        给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
//
//        示例 1：
//
//        输入：digits = "23"
//        输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
//        示例 2：
//
//        输入：digits = ""
//        输出：[]
//        示例 3：
//
//        输入：digits = "2"
//        输出：["a","b","c"]
//
//
//        提示：
//
//        0 <= digits.length <= 4
//        digits[i] 是范围 ['2', '9'] 的一个数字。

// 解题思路：
// 确认字符与数字的映射关系 - 哈希表
// 每次选一个键，每个键代表几个字母，找所有键的全排列即可
// 全排列问题使用深度优先搜索 dfs，收集叶子节点的值即可

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LetterCombinations {
    List<String> ret = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    Map<Character, char[]> map = new HashMap<>();
    char[] chArr;
    int n = 0;
    public List<String> letterCombinations(String digits) {
        if(digits.equals("")) return ret;
        n = digits.length();
        map.put('2', new char[] {'a', 'b', 'c'});
        map.put('3', new char[] {'d', 'e', 'f'});
        map.put('4', new char[] {'g', 'h', 'i'});
        map.put('5', new char[] {'j', 'k', 'l'});
        map.put('6', new char[] {'m', 'n', 'o'});
        map.put('7', new char[] {'p', 'q', 'r', 's'});
        map.put('8', new char[] {'t', 'u', 'v'});
        map.put('9', new char[] {'w', 'x', 'y', 'z'});
        chArr = digits.toCharArray();
        dfs(chArr, 0);
        return ret;
    }
    public void dfs(char[] chArr, int pos){
        if(pos >= n){
            ret.add(String.valueOf(path));
            return;
        }
        char[] tmp = map.get(chArr[pos]);
        for (char c : tmp) {
            path.append(c);
            dfs(chArr, pos + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }

    String[] keys = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations2(String digits) {
        if(digits.equals("")) return ret;
        n = digits.length();
        chArr = digits.toCharArray();
        dfs2(chArr, 0);
        return ret;
    }
    public void dfs2(char[] chArr, int pos){
        if(pos == n){
            ret.add(new String(path));
            return;
        }
        int i = chArr[pos] - '0';
        char[] tmp = keys[i].toCharArray();
        for(char c : tmp){
            path.append(c);
            dfs(chArr, pos + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}
